// import { insertSort2, insertSortEnhance } from './insertSrot'

/**
 * NOTE: 归并排序, 空间换时间, O(NlogN),
 * k, i, j 三个索引
 * 对 arr[l...r] 的范围进行排序,
 * 将数组切分, 直到分裂到只有一个元素, 那么再向上进行归并
 */
export function mergeSort(arr: number[]) {
  __mergeSort(arr, 0, arr.length - 1)
}

function __mergeSort(arr: number[], l: number, r: number) {
  // 当只有一个元素或者是没有元素的时候就结束分裂
  if (l >= r) {
    return
  }
  // if (r - l <= 10) {
  //   return insertSort2(arr, l, r)
  // }
  let mid = l + Math.floor((r - l) / 2)
  // 二分分裂的 O(logN)
  __mergeSort(arr, l, mid)
  __mergeSort(arr, mid + 1, r)

  if (arr[mid] > arr[mid + 1]) { // 只有当 arr[mid] max 位置的 小于 arr[mid+1] min 时, 才进行 merge
    // 将所有的都分裂之后, 进行向上的归并
    merge(arr, l, mid, r) // O(N)
  }
}

function merge(arr: number[], l: number, mid: number, r: number) {
  // 开辟一个临时空间进行辅助,
  let tmp = new Array(r - l + 1)
  // 将 arr[l...r] 的数据复制到 tmp 中
  for (let i = l; i <= r; i++) {
    // 从 0 开始
    tmp[i - l] = arr[i]
  }

  let i = l // i 索引为归并之中的右边的索引
  let j = mid + 1 // j 为左边的索引
  for (let k = l; k <= r; k++) {
    // 判断边界, 如果 i 先到了边界 mid, 那么说明要 j 要向后移动
    if (i > mid) {
      arr[k] = tmp[j - l]
      j++
    } else if (j > r) { // 如果 j 到了边界 r 那么要移动 i,
      arr[k] = tmp[i - l]
      i++
    } else if (tmp[i - l] < tmp[j - l]) { // 如果都没有到边界, 且 i < j 位置
      arr[k] = tmp[i - l] // 将 arr[k] 位置的值替换
      i++
    } else { // 如果都没有到边界 且 i >= j 位置的值
      arr[k] = tmp[j - l] // arr[k] 位置的值为 j 位置的值
      j++
    }
  }
}

// 自底向上: 没有通过索引直接获取数据,
// 那么可以通过这个给链表进行排序
export function mergeSortBU(arr: number[]) {
  for (let sz = 1; sz <= arr.length; sz += sz) {
    for (let i = 0; (i + sz) < arr.length; i += sz * 2) {
      // 对: arr[i...(i+sz-1)] 和 arr[i+sz, i+2*zs-1]
      merge(arr, i, i + sz - 1, Math.min(i + sz * 2 - 1, arr.length - 1))
    }
  }
}
